1. Field of the Invention
This invention relates to multiplier circuits and, more particularly, to methods and apparatus for constructing multipliers using carry save adders having an area efficient floor plan.
2. History of the Prior Art
Various arrangements for providing fast multiplying circuits for use in computers have been proposed. In general, these circuits may be used in either integer multiplication or in generating the mantissa in floating point multiplication. In the most basic case, the product of two n-bit binary operands is realized by determining a number of partial products each of which is offset by one bit to the left from the preceding partial product and then summing those partial products to reach a result.
In order to rapidly sum the partial products in this basic case, each of the individual columns of bits is summed individually in parallel with all others to produce a result which is a sum and a carry. However, binary adder stages are in general capable of handling only two inputs at a time so it takes some time to add each individual column. In order to reduce the time, a tree arrangement has been suggested in which the individual partial products are grouped in pairs and the groups summed in parallel by carry-save adders. These adders use as inputs carries from preceding stages so that even though the computations are carried out in parallel, the addition of each two bits of the partial product in a column requires sufficient time for the carry from the preceding stage to propagate. The results of the summations of these partial products are again grouped in pairs and the groups summed in parallel in the same manner by additional carry-save adders. This process continues until the last two partial products are summed to produce a product. High Speed Multiplier Using a Redundant Binary Adder Tree, Harata et al, IEEE Journal of Solid-State Circuits, Vol SC-22, No. 1, February 1987, describes such a circuit.
The circuits described in the above-mentioned article, although efficient in accomplishing their operations, are inefficient in the use of silicon. This is because the adders at different levels of addend summation are of unequal length, the lengths of the adders at higher levels being longer. When the length of the adders varies, the silicon occupied by the multiplier circuits varies radically over the area of the circuitry. Consequently, a great deal of the silicon area is wasted. In an attempt to produce the most regular implementation possible, it has been proposed by Vuillemin and Luk in an article entitled "Recursive Implementation of Optimal Time VLSI Integer Multipliers," published in VSLI '83, by Elsevier Science Publishers B.V., (hereinafter referred to as Vuillemin) to use individual adders which include two full adder circuits arranged to sum four separate inputs and a carry from the previous stage and to carry forward another carry from the previous stage to produce a pair of results and a pair of carries from each stage. Four individual partial products may be summed simultaneously using these four input adders, and the number of individual adders at all levels of addend summation may be made to have an equal length of 2n bits. Although this produces a regular area for the circuitry, the amount of area used is still much larger than is necessary for the operation, resulting in a large waste of silicon space and enlarging the chip needed to carry the circuitry.